package book;

public class BuyChickenRecursion {
    static int k, m, n;
    static String a[];
    static int x[], y[];
    static int[] b; // b[i]保存第i种鸡买了多少只

    // 递归求解：m元买n只鸡问题
    static void buy(int i, int t, int u) {
        if (i == k - 1) {
            b[i] = (m - u) / x[i];
            if (u + b[i] * x[i] == m && t + b[i] * y[i] == n) {
                System.out.print("解:");
                for (int j = 0; j < k; j++)
                    System.out.print(" " + a[j] + (b[j] * y[j]) + "只");
                System.out.println();
            }
            return;
        }
        // 方案搜索：买1单位，2单位，3……
        for (b[i] = 0; b[i] < n; b[i]++) {
            if (u + b[i] * x[i] > m || t + b[i] * y[i] > n)
                break; // 当总只数或者总价钱超额时停止搜索

            // 递归搜索下一种鸡的购买方案
            buy(i + 1, t + b[i] * y[i], u + b[i] * x[i]);
        }
    }

    public static void main(String[] args) {
        k = 3; m = n = 100;
        a = new String[] { "公鸡", "母鸡", "小鸡" };
        x = new int[] { 5, 3, 1};
        y = new int[] { 1, 1, 3 };
        b = new int[k];
        buy(0, 0, 0);
    }
}
